package com.wj.tree;

import com.wj.linear.Queue;

/**
 * @author wen.jie
 * @date 2021/8/23 10:40
 * 二叉查找树
 */
public class BinaryTree<Key extends Comparable<Key>, Value> {
    //根节点
    private Node root;

    private int N;

    public int size(){
        return N;
    }

    private class Node {
        //存储键
        public Key key;
        //存储值
        private Value value;
        //记录左子结点
        public Node left;
        //记录右子结点
        public Node right;

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    /**
     * 向指定的树x中添加key-value,并返回添加元素后新的树
     * @author wen.jie
     * @date 2021/8/23 10:56
     */
    private Node put(Node x, Key key, Value value) {
        //x子树为空
        if (x == null) {
            N++;
            return new Node(key, value, null , null);
        }

        //x子树不为空
        int cmp = key.compareTo(x.key);

        if (cmp > 0) {
            x.right = put(x.right, key, value);
        }else if(cmp < 0){
            x.left = put(x.left, key, value);
        }else {
            x.value = value;
        }
        return x;
    }

    /**
     * @author wen.jie
     * @date 2021/8/23 11:02
     * 查找树中指定key对应的value
     */
    public Value get(Key key){
        return get(root, key);
    }

    private Value get(Node x, Key key) {
        //x子树为空
        if (x == null) return null;
        //x子树不为空
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            return get(x.right, key);
        }else if(cmp < 0){
            return get(x.left, key);
        }else {
            return x.value;
        }
    }

    /**
     * @author wen.jie
     * @date 2021/8/23 11:28
     * 删除树中key对应的value
     */
    public void delete(Key key){
        root = delete(root, key);
    }

    /**
     * @author wen.jie
     * @date 2021/8/23 11:28
     * 删除指定树x中的key对应的value,并返回删除后的新树
     */
    public Node delete(Node x, Key key){
        if (x == null) return null;

        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            //找x节点的右子树
            x.right = delete(x.right, key);
        }else if(cmp < 0){
            //找x节点的左子树
            x.left = delete(x.left, key);
        }else {
            N--;
            if(x.right == null) return x.left;
            if(x.left == null) return x.right;

            //得找到右子树中最小的节点
            Node minNode = min(x.right);

            //删除右子树最小的节点,返回新的右子树
            Node n = deleteMin(x.right);

            //让x节点的左子树成为minNode的左子树
            minNode.left = x.left;
            //让新的右子树成为minNode的右子树
            minNode.right = n;
            return minNode;
        }

        return x;
    }

    /**
     * @author wen.jie
     * @date 2021/8/23 16:47
     * 删除指定树中最小的节点,并返回新的树
     */
    private Node deleteMin(Node x){
        if(x.left == null) return x.right;
        x.left = deleteMin(x.left);
        return x;
    }

    /**
     * @author wen.jie
     * @date 2021/8/23 16:43
     * 返回指定树中最小的节点
     */
    private Node min(Node x){
        if(x.left == null) return x;
        return min(x.left);
    }

    /**
     * @author wen.jie
     * @date 2021/8/23 16:43
     * 返回二叉查找树中最小的key
     */
    private Key min(){
        return min(root).key;
    }

    private Node max(Node x){
        if(x.right == null) return x;
        return max(x.right);
    }

    private Key max(){
        return max(root).key;
    }

    /**
     * @author wen.jie
     * @date 2021/8/23 17:26
     * 前序遍历获取整个树中所有的键
     */
    public Queue<Key> preErgodic() {
        Queue<Key> keys = new Queue<>();
        preErgodic(root, keys);
        return keys;
    }

    private void preErgodic(Node x, Queue<Key> keys){
        if(x == null) return;
        keys.enqueue(x.key);
        if(x.left != null) preErgodic(x.left, keys);
        if(x.right != null) preErgodic(x.right, keys);
    }

    /**
     * @author wen.jie
     * @date 2021/8/23 17:26
     * 中序遍历获取整个树中所有的键
     */
    public Queue<Key> midErgodic() {
        Queue<Key> keys = new Queue<>();
        midErgodic(root, keys);
        return keys;
    }

    private void midErgodic(Node x, Queue<Key> keys){
        if(x == null) return;
        if(x.left != null) midErgodic(x.left, keys);
        keys.enqueue(x.key);
        if(x.right != null) midErgodic(x.right, keys);
    }

    /**
     * @author wen.jie
     * @date 2021/8/23 17:26
     * 后序遍历获取整个树中所有的键
     */
    public Queue<Key> afterErgodic() {
        Queue<Key> keys = new Queue<>();
        afterErgodic(root, keys);
        return keys;
    }

    private void afterErgodic(Node x, Queue<Key> keys){
        if(x == null) return;
        if(x.left != null) afterErgodic(x.left, keys);
        if(x.right != null) afterErgodic(x.right, keys);
        keys.enqueue(x.key);
    }

    public Queue<Key> layerErgodic(){
        Queue<Key> keys = new Queue<>();
        Queue<Node> nodes = new Queue<>();
        nodes.enqueue(root);

        while (!nodes.isEmpty()){
            Node node = nodes.dequeue();
            keys.enqueue(node.key);
            if(node.left != null) nodes.enqueue(node.left);
            if(node.right != null) nodes.enqueue(node.right);
        }
        return keys;
    }

    /**
     * @author wen.jie
     * @date 2021/8/23 17:56
     * 求整个树的最大深度
     */
    public Integer maxDepth(){
        return maxDepth(root);
    }

    private Integer maxDepth(Node x){
        if (x == null)  return 0;
        int max = 0;
        int maxL = 0;
        int maxR = 0;
        //2.计算左子树的最大深度；
        if (x.left != null) {
            maxL = maxDepth(x.left);
        }
        //3.计算右子树的最大深度；
        if (x.right != null) {
            maxR = maxDepth(x.right);
        }
        //4.当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1
        max = maxL > maxR ? maxL + 1 : maxR + 1;
        return max;
    }
}
